package Tests;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.TreeMap;

import CSP.Constraint;

public class testerei2 {
	private static HashMap<String, Constraint> constraints;
	private static ArrayList<String> outputBT;
	
	public static void main(String[] args) {		
		constraints = new HashMap<String, Constraint>();
		outputBT = new ArrayList<String>();
		String s = "Martin: Christine, !Gerrit. Christine: !Anton, Bernd. Klaus: Olaf. Simon: Lars, Anton. Gerrit: Lars, !Martin, !Christine, !Simon";
		int variables[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
		String domainBT[] = {"Martin", "Christine", "Olaf", "Bernd", "Klaus", "Paul", "Anton", "Simon", "Gerrit", "Lars"};
		TreeMap<Integer, String> assigns = new TreeMap<Integer, String>();
		
		List<Integer> variablesList = new ArrayList<Integer>();
		
		for (int i : variables) 
			variablesList.add(i);
		
		List<String> domainList = new ArrayList<String>();
		
		for(String st : domainBT)
			domainList.add(st.toLowerCase());		
		
		System.out.println(generateConstraints(s));
		
		Backtracking(assigns, variablesList, domainList);
		
		System.out.println("-----------------------------------\n");
		int i = 0;
		for(String val : outputBT)
		{
			System.out.println(i + ") " + val);
			i++;
		}

		System.out.println("-----------------------------------\n");
		//System.out.println(assigns);
		
		System.out.println("-----------------------------------\n");
		System.out.println(constraints);
	}
	
	public static String generateConstraints(String s) {
		String sub;
		String name;
		Constraint constraint;
		Constraint tmpConstraint;
		int constraintCount = 0;
		String constString = "";
		
		s = s.replaceAll("\\s+", "");
		s = s.toLowerCase();
		
		if(!s.endsWith("."))
			s = s.concat(".");
		
		
		
		while(s.contains("."))
		{
			constraintCount++;
			sub = s.substring(0, s.indexOf("."));
			s = s.substring(s.indexOf(".") + 1);
			
			sub = sub + ",";
			
			name = sub.substring(0, sub.indexOf(":"));
			sub = sub.substring(sub.indexOf(":") + 1);
			
			if(constraints.containsKey(name))
			{
				constraint = constraints.get(name);
				if(constraint.getID() != 42 && constraint.getID() < constraintCount)
					constraint.changeID(constraintCount);
			}
			else
				constraint = new Constraint(name, constraintCount);
			
			if(constString.length() == 0)
				constString = "(1) " + name;
			else
				constString += "\n(" + constraintCount + ") " + name;
			
			while(sub.contains(",")) 
			{
				name = sub.substring(0, sub.indexOf(","));
				sub = sub.substring(sub.indexOf(",") + 1);
				
				if(name.startsWith("!"))
					constraint.addDisallowed(name.substring(1));
				else
					constraint.addAllowed(name);
			}
			
			constraints.put(constraint.getName(), constraint);
			
			// Create Constraints-String
			if(constraint.getAllowed().size() != 0)
				constString += " sitzt neben ";
			for(String sn : constraint.getAllowed())
				constString += sn + ", ";
			
			
			// Add transitive allowed-constraints
			for(String allowed : constraint.getAllowed()) {
				if(constraints.containsKey(allowed)) {
					tmpConstraint = constraints.get(allowed);
					tmpConstraint.addAllowed(constraint.getName());
				}
				else {
					tmpConstraint = new Constraint(allowed, constraintCount);
					tmpConstraint.addAllowed(constraint.getName());
				}
				constraints.put(allowed, tmpConstraint);					
			}
			
			if(constraint.getAllowed().size() != 0)
				constString += "aber nicht neben ";
			for(String sn : constraint.getDisallowed())
				constString += sn + ", ";
			
			// Add transitive disallowed-constraints
			for(String disallowed : constraint.getDisallowed()) {
				if(constraints.containsKey(disallowed)) {
					tmpConstraint = constraints.get(disallowed);
					tmpConstraint.addDisallowed(constraint.getName());
				}
				else {
					tmpConstraint = new Constraint(disallowed, constraintCount);
					tmpConstraint.addDisallowed(constraint.getName());
				}
				constraints.put(disallowed, tmpConstraint);					
			}
			
			// , am Ende entfernen
			constString = constString.substring(0, constString.lastIndexOf(","));
		}
		
		return constString;
	}
	
	public static TreeMap<Integer, String> Backtracking(TreeMap<Integer, String> assigns, List<Integer> variables, List<String> domainBT) {
		if(variables.size() == 0 || domainBT.size() == 0)
			return assigns;
		
		int current = variables.get(0);
		outputBT.add("Select " + current);
		
		int check = 42;
		TreeMap<Integer, String> result;		
		ArrayList<String> alternatives = new ArrayList<String>();
		
		// Check for first assigns (wishes)
		for(int i = 0; i < domainBT.size(); i++)
		{			
			// Constraints-check
			if(current == 1)	// Initial assignment (seat 1)
				check = checkConstraints(null, domainBT.get(i), null);
			else if(variables.size() == 1)	// last assignment (seat 10 e.g.)
				check = checkConstraints(assigns.get(assigns.lastKey()), domainBT.get(i), assigns.get(assigns.firstKey()));
			else	// normal assignment				
				check = checkConstraints(assigns.get(assigns.lastKey()), domainBT.get(i), null);
				
			
			switch(check) 
			{			
				case 0: 
					outputBT.add(current + " = " + domainBT.get(i) + " not consistent (" + constraints.get(domainBT.get(i)).getID() +")");
					break;
				
				case 1:
					// Adding assignment
					assigns.put(current, domainBT.get(i));
					
					// previous Strings are not consistent
					for(String s : alternatives)
						outputBT.add(current + " = " + s + " not consistent (" + constraints.get(domainBT.get(i)).getID() +")");
						
					outputBT.add(current + " = " + domainBT.get(i) + " consistent");
					variables.remove(0);
					domainBT.remove(domainBT.get(i));				
				
					// Recursion
					result = Backtracking(assigns, variables, domainBT);
				
					// Failure-Fall
					if(result != null)
						return result;
				
					// Backtrack-Fall
					variables.add(0, assigns.lastKey());
					domainBT.add(i, assigns.get(assigns.lastKey()));
					assigns.remove(current);
					outputBT.add("Backtrack");
					outputBT.add("Select " + current);
					break;
				
				case 2:
					alternatives.add(domainBT.get(i));
					break;
			}
		}
		// Check alternatives
		for(String s : alternatives)
		{
			// Adding assignment
			assigns.put(current, s);
			outputBT.add(current + " = " + s + " consistent");
			variables.remove(0);
			domainBT.remove(s);			
				
			// Recursion
			result = Backtracking(assigns, variables, domainBT);
				
			// Failure-Fall
			if(result != null)
					return result;
				
			// Backtrack-Fall
			variables.add(0, assigns.lastKey());
			domainBT.add(0, assigns.get(assigns.lastKey()));
			assigns.remove(current);
			outputBT.add("Backtrack");
		}
		return null;
	}
	
	public static int checkConstraints(String left, String person, String right) {
		if(checkLeft(left, person) == 0 || checkRight(person, right) == 0)
			return 0;
		if(checkLeft(left, person) == 1 && checkRight(person, right) == 1)
			return 1;
		
		return 2;
	}
	
	public static int checkLeft(String left, String person) {		
		if(left == null)
			return 1;

		Constraint cons;
		if(constraints.containsKey(person))
			cons = constraints.get(person);	
		else 
		{
			cons = new Constraint(person);
			constraints.put(person, cons);
		}
		
		return cons.consistent(left);
	}
	
	public static int checkRight(String person, String right) {
		if(right == null)
			return 1;
		
		Constraint cons;
		if(constraints.containsKey(person))
			cons = constraints.get(person);	
		else 
		{
			cons = new Constraint(person);
			constraints.put(person, cons);
		}
		
		return cons.consistent(right);
	}
}
